//树可以看成是一个连通且 无环 的 无向 图。 
//
// 给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信
//息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。 
//
// 请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的边。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入: edges = [[1,2], [1,3], [2,3]]
//输出: [2,3]
// 
//
// 示例 2： 
//
// 
//
// 
//输入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
//输出: [1,4]
// 
//
// 
//
// 提示: 
//
// 
// n == edges.length 
// 3 <= n <= 1000 
// edges[i].length == 2 
// 1 <= ai < bi <= edges.length 
// ai != bi 
// edges 中无重复元素 
// 给定的图是连通的 
// 
// Related Topics 深度优先搜索 广度优先搜索 并查集 图 
// 👍 404 👎 0

package com.cute.leetcode.editor.cn;
public class RedundantConnection {
    public static void main(String[] args) {
        Solution solution = new RedundantConnection().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 我感觉就是将一条边去掉之后，遍历剩下的所有节点，如果能访问到的话就说明当前边可以去掉
         * 因为是无向图，所有一个点的入度至少为1（考虑的是双向的连接）
         * 可以去掉的边绝对是构成了环路
         *
         * 并查集算法的参考链接：https://zhuanlan.zhihu.com/p/93647900/
         * 并查集问题，查询两个元素是否属于同一个集合，只需要查询其代表元素是否相同
         * 开始是各个顶点都是自己的代表元素
         * 遍历边的时候对其进行合并，如果一条边的两个点在合并时发现代表元素是一样的，那么这两个顶点之间之前就可以联系上了
         * 所以这条边加上去就是多余的了
         * 代表元素不同的话将左顶点依附于右顶点
         * 举例：将左节点的代表节点设置为右节点的方式
         * 读取顺序为[[1,2], [3,4], [3,2], [1,4], [1,5]]
         * 当前parent[0, 1, 2, 3, 4, 5]
         * 当前index [0, 1, 2, 3, 4, 5]
         *  1.读取[1,2]
         *      当前parent[0, 2, 2, 3, 4, 5]
         *      当前index [0, 1, 2, 3, 4, 5]
         *  2.读取[3,4]
         *     当前parent[0, 2, 2, 4, 4, 5]
         *     当前index [0, 1, 2, 3, 4, 5]
         *  3.读取[3,2]
         *     当前parent[0, 2, 2, 4, 2, 5]
         *     当前index [0, 1, 2, 3, 4, 5]
         *  4.读取[1,4]
         *      1的代表节点为2，且4的代表节点也是2，所以[1,4]构成的边是多余的
         *
         */
        public int[] findRedundantConnection(int[][] edges) {
            //节点中没有0这个元素
            int[] parent = new int[edges.length+1];
            //开始时将所有的点看作是独立的，每个点的代表元素都是自己
            for (int i = 1; i <= edges.length; i++) parent[i] = i;

            for (int[] edge : edges){
                //查找一条边两个顶点的代表元素
                int index1 = find(parent, edge[0]);
                int index2 = find(parent, edge[1]);
                //如果两个顶点的代表元素是同一个的话，而且是无向图，说明这两个点之间不需要形成边就可以访问到，所以此边多余
                if (index1 == index2) return edge;
                //如果代表顶点不同，就将左边挂到右边（帮派合并，老大成老二）
                parent[index1] = index2;
            }
            return new int[]{0,0};
        }

        /**
         * 查找代表节点，只要不到底就一直查下去就完了
         */
        public int find(int[] parent, int index){
            if (index == parent[index]) return index;
            else return find(parent, parent[index]);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}